home *** CD-ROM | disk | FTP | other *** search
/ The Arsenal Files 6 / The Arsenal Files 6 (Arsenal Computer).ISO / prg_casm / tran20.zip / TRAN.DOC < prev    next >
Text File  |  1996-01-09  |  20KB  |  763 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  
  10.  
  11.  
  12.  
  13.  
  14.  
  15.  
  16.  
  17.  
  18.  
  19.  
  20.  
  21.  
  22.  
  23.  
  24.  
  25.  
  26.  
  27.  
  28.                            TRAN PROGRAMMER'S MANUAL
  29.                                   VERSION 2.0
  30.  
  31.                      (TechniLib Random Number Generators)
  32.  
  33.  
  34.                                TechniLib Company
  35.  
  36.  
  37.  
  38.  
  39.  
  40.  
  41.  
  42.  
  43.  
  44.  
  45.  
  46.  
  47.  
  48.  
  49.  
  50.  
  51.  
  52.  
  53.  
  54.  
  55.  
  56.  
  57.  
  58.  
  59.  
  60.  
  61.                 Copyright 1995, 1996 by TechniLib (TM) Company
  62.                               All Rights Reserved
  63.  
  64.  
  65.  
  66.                          TERMS OF USE AND DISTRIBUTION
  67.  
  68.  
  69.        TRAN is a shareware product; therefore, unregistered copies of TRAN
  70.   are made available free of charge so that potential purchasers will have
  71.   the opportunity to examine and test the software before committing payment.
  72.   Distribution of unregistered copies of TRAN to other potential users is
  73.   also permitted and appreciated.  However, usage and distribution of TRAN
  74.   must conform to the following conditions.  In the following statement, the
  75.   term "commercial distribution," includes shareware distribution.
  76.  
  77.   1) TRAN and accompanying software must be distributed together in copies of
  78.   the original archive provided by TechniLib.  Neither the archive nor
  79.   individual files therein may be modified.
  80.  
  81.   2) The TRAN archive may be distributed in combination with other shareware
  82.   products; however, the TRAN archive may not be distributed with other
  83.   commercially distributed software without written consent of TechniLib.
  84.  
  85.   3) Copies of TRAN which have been used to develop software for commercial
  86.   distribution must be registered before such software is marketed.  Copies
  87.   of TRAN which have been used to develop noncommercial software must be
  88.   registered if such software is to be regularly used either by the developer
  89.   or others.
  90.  
  91.   4) Commercially distributed software must embed TRAN procedures in the
  92.   software code.  Files contained in the TRAN archive may not be placed in
  93.   the distribution media.
  94.  
  95.   5) TRAN is designed to offer a set of services to other executable code.
  96.   TRAN may not be used to develop software for commercial distribution which
  97.   will essentially offer any of these same services to other executable code.
  98.   Exceptions to this condition require written consent of TechniLib.
  99.  
  100.   6) Rights afforded by registering a single copy of TRAN pertain only to a
  101.   single computer.
  102.  
  103.   7) TRAN may be registered for a fee of $25.00 per copy.  Consult README.DOC
  104.   in the TRAN archive for further instructions regarding registration.
  105.  
  106.  
  107.                             DISCLAIMER OF WARRANTY
  108.  
  109.  
  110.        TRAN AND ALL ACCOMPANYING SOFTWARE AND LITERATURE ARE DISTRIBUTED WITH
  111.   THE EXCLUSION OF ANY AND ALL IMPLIED WARRANTIES, AND WITH THE EXCLUSION OF
  112.   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
  113.   TechniLib SHALL HAVE NO LIABILITY FOR SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
  114.   DAMAGES RESULTING FROM THE USE OF TRAN OR ACCOMPANYING MATERIALS.  The user
  115.   assumes the entire risk of using this software.
  116.  
  117.  
  118.  
  119.  
  120.  
  121.  
  122.                 Copyright 1995, 1996 by TechniLib (TM) Company
  123.                               All Rights Reserved
  124.  
  125.  
  126.  
  127.  
  128.  
  129.  
  130.                                  Introduction
  131.                                  ------------
  132.  
  133.  
  134.        TRAN is a library of procedures designed to generate random numbers
  135.   for various probability densities.  TRAN specifically generates random
  136.   numbers for the uniform, normal (Gaussian), gamma, beta, Cauchy
  137.   (Lorentzian), binomial, geometric, Pascal (negative binomial), and poisson
  138.   distributions.  Random variables for other popular distributions can
  139.   generally be obtained from transformations of these.  This document
  140.   explains how to use such methods to generate variates for the chi-squared,
  141.   F, T, exponential, Gumbel, Pareto, Weibull, and logistic distributions.
  142.        TRAN is exceptionally fast because it is uses efficient algorithms
  143.   that are entirely written in assembly language.  The code is also designed
  144.   to fully utilize the parallel processing capabilities of the Pentium
  145.   processor.  Speed is potentially an important consideration since random
  146.   number generators can be called with great frequency in simulation
  147.   programs.  A considerable amount of arithmetic is often needed to generate
  148.   random numbers; consequently, inefficient code can be costly in terms of
  149.   CPU time.
  150.        TRAN code is extremely compact.  Notwithstanding its many functions,
  151.   TRAN occupies a little over 3K of RAM.  Such compactness is another benefit
  152.   of assembly language.
  153.        TRAN algorithms produce random variables of high quality.  It is well
  154.   known that many random number generators produce numbers failing to meet
  155.   important tests of randomness.  TRAN's uniform variate generator uses dual
  156.   linear congruential generators and a shuffle table to produce high-quality
  157.   variates.  Since all of the other generators are based upon the uniform
  158.   generator, they too possess a high degree of randomness.  All continuous
  159.   generators in TRAN have a period of 2.3058e18.
  160.        The TRAN archive contains libraries for Microsoft, Borland, and Watcom
  161.   languages.  These libraries are compatible with both DOS and Windows.
  162.   Libraries for Microsoft are in the file MICROSOF.ZIP.  Libraries for
  163.   Borland are in BORLAND.ZIP.  Watcom libraries are in WATCOM.ZIP.  These
  164.   archives contain files called TRAN.LIB and REGISTRD.ZIP.  TRAN.LIB contains
  165.   random number procedures for the small memory model.  REGISTRD.ZIP contains
  166.   libraries for small, medium, compact, and large memory models.
  167.   REGISTRD.ZIP is password protected.  The password is supplied upon
  168.   registration of TRAN.  Refer to README.DOC for registration information.
  169.   TRAN.LIB should be used to test and examine the software before
  170.   registration.
  171.        REGISTRD.ZIP contains files named TRANx.LIB where x equals either s,
  172.   m, c, or l; corresponding to the small, medium, compact, and large memory
  173.   models.  The remaining files in REGISTRD.ZIP are called FPUTRANx.LIB for x
  174.   = s, m, c, and l.  These libraries are like the TRANx libraries except they
  175.   assume the presence of a math coprocessor.  They are smaller and faster
  176.   than the TRANx libraries.
  177.  
  178.  
  179.  
  180.  
  181.  
  182.  
  183.  
  184.  
  185.  
  186.  
  187.                                        1
  188.  
  189.  
  190.  
  191.  
  192.  
  193.  
  194.        The following C prototypes summarize the major procedures in TRAN:
  195.  
  196.   Procedure                             Purpose
  197.   ---------                             -------
  198.   void setseed(long seed)               Initialize all generators
  199.   double rndu(void)                     Generate uniform variate on (0,1)
  200.   double rnd_normal(void)               Generate standard normal variate
  201.   void parm_gamma(double r)             Parameterize gamma generator
  202.   double rnd_gamma(void)                Generate gamma variate
  203.   void parm_beta(double a, double b)    Parameterize beta generator
  204.   double rnd_beta(void)                 Generate beta variate
  205.   double rnd_cauchy(void)               Generate standard Cauchy variate
  206.   void parm_binomial(ulong n, double p) Parameterize binomial generator
  207.   ulong rnd_binomial(void)              Generate binomial variate
  208.   void parm_pascal(ulong n, double p)   Parameterize Pascal generator
  209.   ulong rnd_pascal(void)                Generate Pascal variate
  210.   void parm_poisson(double theta)       Parameterize poisson generator
  211.   ulong rnd_poisson(void)               Generate poisson variate
  212.  
  213.        Observe that the generator functions never accept arguments.  If
  214.   parameters are needful, then the generator is parameterized by a call to a
  215.   separate function.  This approach enables faster execution.
  216.        The parameterization functions do not check arguments for validity;
  217.   consequently, error codes are not returned.  Invalid parameters will
  218.   generally lead to floating point unit (FPU) exceptions.
  219.        See EXAMPLE.C in the TRAN archive for an example program using TRAN.
  220.  
  221.  
  222.                                Initializing TRAN
  223.                                -----------------
  224.  
  225.  
  226.        All TRAN generators should be initialized by a call to setseed().  The
  227.   prototype for this function is:
  228.  
  229.   void setseed(ulong seed);
  230.  
  231.   where seed is any nonzero number.  If setseed() is never called, or called
  232.   with seed = 0, then a seed value of 1 is used instead.  A unique sequence
  233.   of random numbers is associated with each seed value.
  234.        Because of the nature of probability computations, extremely small
  235.   numbers are sometimes obtained as intermediate results.  These small
  236.   numbers are typically harmless, but can generate FPU exceptions unless the
  237.   FPU is appropriately configured.  The control word in the FPU should be set
  238.   to mask exceptions for underflow and denormalized operands.  TRAN contains
  239.   two procedures to handle this task.  These are setfpucw() and resetfpucw().
  240.   Neither procedure has parameters nor return values.  setfpucw()
  241.   appropriately sets the FPU control word for TRAN.  resetfpucw() restores
  242.   the original control word.
  243.  
  244.  
  245.  
  246.  
  247.  
  248.  
  249.  
  250.  
  251.                                        2
  252.  
  253.  
  254.  
  255.  
  256.  
  257.  
  258.                     TRAN Generators for Continuous Variates
  259.                     ---------------------------------------
  260.  
  261.  
  262.        This section discusses variates from continuous distributions which
  263.   can be directly simulated with TRAN.  Later sections discuss
  264.   transformations which enable simulation of other distributions.
  265.  
  266.  
  267.   Uniform Variates
  268.   ----------------
  269.  
  270.         Uniform variates are returned by rndu().  The return values are
  271.   always between zero and one.  Zero and one are never themselves returned.
  272.   Uniform random numbers over (a, b) can be generated with:
  273.  
  274.   x = (b - a) rndu() + a
  275.  
  276.  
  277.   Normal (Gaussian) Variates
  278.   --------------------------
  279.  
  280.        Standard normal variates are returned by rnd_normal().  A normal
  281.   variate with mean µ and standard deviation σ can be generated with:
  282.  
  283.   x = σ rnd_normal() + µ
  284.  
  285.  
  286.   Gamma Variates
  287.   --------------
  288.  
  289.        The gamma density has the form:
  290.  
  291.            r          r-1  -Θx
  292.   f(x) = [Θ  / Γ(a)] x    e              x, r, Θ > 0
  293.  
  294.   where Γ is the complete gamma function.  TRAN only generates values
  295.   corresponding to Θ = 1 because variates for other Θ can be obtained by
  296.   dividing TRAN return values by Θ.
  297.        The gamma generator must first be parameterized by a call to
  298.   parm_gamma().  This function informs the generator as to the appropriate
  299.   value of r.  The C prototype is:
  300.  
  301.   void parm_gamma(double r);
  302.  
  303.   rnd_gamma() may then be called to obtain the gamma variates.
  304.        Unlike many generators, rnd_gamma() can generate values for r < 1.
  305.        For small integer values of r, it may be faster to generate gamma
  306.   variates with:
  307.  
  308.   x = -log[U1 U2 ... Ur] / Θ
  309.  
  310.   where log() is the natural log, and U1...Ur are uniform variates in (0,1).
  311.  
  312.  
  313.  
  314.  
  315.                                        3
  316.  
  317.  
  318.  
  319.  
  320.  
  321.  
  322.   Beta Variates
  323.   -------------
  324.  
  325.        The beta density has the form:
  326.  
  327.                        a-1        b-1
  328.   f(x) = [1 / ß(a,b)] x    (1 - x)       a, b > 0; 0 < x < 1
  329.  
  330.   where ß() is the beta function.  To generate beta variates, one must first
  331.   parameterize the generator with a call to parm_beta().  The function has C
  332.   prototype:
  333.  
  334.   void parm_beta(double a, double b);
  335.  
  336.   Beta variates can then be obtained by calling rnd_beta().
  337.        Unlike many beta generators, rnd_beta() can generate variates when
  338.   either a < 1 or b < 1 or both.
  339.  
  340.  
  341.   Cauchy (Lorentzian) Variates
  342.   ----------------------------
  343.  
  344.        The Cauchy density is specified by:
  345.  
  346.                      1
  347.   f(x) =  ----------------------         σ > 0
  348.           σπ[1 + [(x - µ) / σ]²]
  349.  
  350.   Cauchy variates for µ = 0 and σ = 1 can be generated by calling
  351.   rnd_cauchy().  For other values of µ and σ, use:
  352.  
  353.   x = σ rnd_cauchy() + µ
  354.  
  355.  
  356.  
  357.  
  358.  
  359.  
  360.  
  361.  
  362.  
  363.  
  364.  
  365.  
  366.  
  367.  
  368.  
  369.  
  370.  
  371.  
  372.  
  373.  
  374.  
  375.  
  376.  
  377.  
  378.  
  379.                                        4
  380.  
  381.  
  382.  
  383.  
  384.  
  385.  
  386.                      TRAN Generators for Discrete Variates
  387.                      -------------------------------------
  388.  
  389.  
  390.        The primary discrete variate generators in TRAN are based upon the
  391.   rejection method using a Cauchy comparison function.  This method is highly
  392.   efficient for most cases; however, even faster methods can be found for
  393.   specific parameter values.  For example, binomial variates under small
  394.   values of n can be generated most efficiently by summing n Bernoulli
  395.   variates.  This approach could be considerably faster than the rejection
  396.   method under small n, but many times slower under large n.
  397.        TRAN includes secondary generators for all discrete distributions to
  398.   accommodate special parameterizations where the rejection method may be
  399.   relatively slow.  The relative speeds of the primary and secondary
  400.   generators can vary from one parameterization to another and from one CPU
  401.   to another.  Unfortunately, there are no "simple" rules offering perfect
  402.   guidance when choosing between generators.  It is therefore recommended
  403.   that choice be based upon experimentation.
  404.  
  405.  
  406.   Binomial Variates
  407.   -----------------
  408.  
  409.        The binomial distribution is defined by:
  410.  
  411.                n!      x       n-x
  412.   f(x) =  ----------- p (1 - p)          0 < p < 1; n > 0; x = 0,1,,,n
  413.           x! (n - x)!
  414.  
  415.        where ! denotes factorial.  To generate binomial variates, one should
  416.   first parameterize the generator with a call to parm_binomial().  This
  417.   function has C prototype:
  418.  
  419.   void parm_binomial(ulong n, double p);
  420.  
  421.   Binomial variates are then generated by calling rnd_binomial().  The
  422.   generator function returns an unsigned long integer.
  423.        The secondary binomial generator computes variates by summing n
  424.   Bernoulli variates.  This generator will be fast when n is small.  It
  425.   should not be used when n is large.  The parameterization function and
  426.   generator have C prototypes:
  427.  
  428.   void parm_binomial2(uint n, double p);
  429.   uint rnd_binomial2(void);
  430.  
  431.        When n is large and np is small, the binomial is well approximated by
  432.   the poisson distribution.  See the section on poisson variates for details.
  433.  
  434.  
  435.  
  436.  
  437.  
  438.  
  439.  
  440.  
  441.  
  442.  
  443.                                        5
  444.  
  445.  
  446.  
  447.  
  448.  
  449.  
  450.   Geometric Variates
  451.   ------------------
  452.  
  453.        The geometric distribution is defined by:
  454.  
  455.                 x
  456.   f(x) = (1 - p) p                       0 < p < 1; x = 0,1,,,
  457.  
  458.  
  459.        The geometric distribution is the special case of the Pascal (negative
  460.   binomial) distribution when r = 1 (see next section).  One may therefore
  461.   generate geometric variates using the Pascal generator.  However, the
  462.   fastest way to generate geometric variates is with:
  463.  
  464.   x = (int)[log(U) / log(1 - p)]
  465.  
  466.   where U is a uniform variate in (0,1), and (int) denotes a type cast which
  467.   truncates the fractional part of its argument.
  468.  
  469.  
  470.   Pascal (Negative Binomial) Variates
  471.   -----------------------------------
  472.  
  473.        The Pascal density has the form:
  474.  
  475.           (x + r - 1)!  r       x
  476.   f(x) =  ------------ p (1 - p)         0 < p < 1; r > 0; x = 0,1,,,
  477.            x! (r - 1)!
  478.  
  479.        The Pascal generator must be parameterized with a call to
  480.   parm_pascal().  This function has C prototype:
  481.  
  482.   void parm_pascal(ulong r, double p);
  483.  
  484.   The variates are then generated by calling rnd_pascal().  The generator
  485.   function returns an unsigned long integer.
  486.        The secondary pascal generator computes variates by summing r
  487.   geometric variates.  This generator will be fast when r is small.  It
  488.   should not be used when r is large.  The parameterization function and
  489.   generator have C prototypes:
  490.  
  491.   void parm_pascal2(uint r, double p);
  492.   uint rnd_pascal2(void);
  493.  
  494.  
  495.  
  496.  
  497.  
  498.  
  499.  
  500.  
  501.  
  502.  
  503.  
  504.  
  505.  
  506.  
  507.                                        6
  508.  
  509.  
  510.  
  511.  
  512.  
  513.  
  514.   Poisson Variates
  515.   ----------------
  516.  
  517.        The poisson density is specified by:
  518.  
  519.           -Θ x
  520.   f(x) = e  Θ / x!                       Θ > 0; x = 0,1,,,
  521.  
  522.        The poisson generator is parameterized with a call to parm_poisson().
  523.   This function has C prototype:
  524.  
  525.   void parm_poisson(double theta);
  526.  
  527.   Poisson variates are obtained by calling rnd_poisson().  This function
  528.   returns an unsigned long integer.
  529.        The secondary poisson generator obtains a poisson variate by counting
  530.   the number of exponential variates necessary to produce a sum greater than
  531.   Θ.  This approach is highly effective when Θ is small.  The C prototypes
  532.   for the parameterization function and generator are:
  533.  
  534.   void parm_poisson2(double theta);
  535.   uint rnd_poisson2(void);
  536.  
  537.        The binomial distribution with parameters n and p converges to a
  538.   poisson with parameter np as p / n converges to zero.  Therefore with large
  539.   n or small p, the cumbersome binomial can be replaced with the poisson.  As
  540.   a general rule, the approximation is "good" when n > 100 and p < .10.
  541.  
  542.  
  543.  
  544.  
  545.  
  546.  
  547.  
  548.  
  549.  
  550.  
  551.  
  552.  
  553.  
  554.  
  555.  
  556.  
  557.  
  558.  
  559.  
  560.  
  561.  
  562.  
  563.  
  564.  
  565.  
  566.  
  567.  
  568.  
  569.  
  570.  
  571.                                        7
  572.  
  573.  
  574.  
  575.  
  576.  
  577.  
  578.                    Generating Variates in the Normal Family
  579.                    ----------------------------------------
  580.  
  581.  
  582.   Chi-Squared Variates
  583.   --------------------
  584.  
  585.        Let G be a gamma variate with parameter r = d / 2, then 2G is a chi-
  586.   squared variate with d degrees of freedom.
  587.        A chi-squared variate with d degrees of freedom can also be generated
  588.   with:
  589.  
  590.         2    2         2
  591.   x = N1 + N2  +...+ Nd
  592.  
  593.   where N1...Nd are standard normal variates.
  594.  
  595.  
  596.   F Variates
  597.   ----------
  598.  
  599.  
  600.        Let B be a beta variate with parameters a = d / 2 and b = n / 2, then:
  601.  
  602.   x = d (1 - B) / nB
  603.  
  604.   is an F variate with n degrees of freedom in the numerator and d degrees of
  605.   freedom in the denominator.
  606.  
  607.  
  608.   T Variates
  609.   ----------
  610.  
  611.        Let F be an F variate with 1 degree of freedom in the numerator and d
  612.   degrees of freedom in the denominator.  Let I = 1 or -1 with 50%
  613.   probability for each (I is independent of F), then a random T variate with
  614.   d degrees of freedom is generated by:
  615.  
  616.          1/2
  617.   x = I F
  618.  
  619.  
  620.  
  621.  
  622.  
  623.  
  624.  
  625.  
  626.  
  627.  
  628.  
  629.  
  630.  
  631.  
  632.  
  633.  
  634.  
  635.                                        8
  636.  
  637.  
  638.  
  639.  
  640.  
  641.  
  642.                   Generating Variates Via the Inverse Method
  643.                   ------------------------------------------
  644.  
  645.  
  646.         Let f() be a probability density with cumulative density F().  Let
  647.   F() be invertible, and let U be a uniform variate in (0,1), then:
  648.  
  649.        -1
  650.   x = F(U)
  651.  
  652.   is distributed according to density f.  In the remainder of this section,
  653.   we present distributions which can be simulated using this method.
  654.  
  655.  
  656.   Exponential Variates
  657.   --------------------
  658.  
  659.             -Θx
  660.   f(x) = Θ e                             x, Θ > 0
  661.  
  662.   generator:  x = -log(U) / Θ
  663.  
  664.        Exponential variates can also be generated from the gamma
  665.   distribution.  The exponential is a special case of the gamma with r = 1.
  666.  
  667.  
  668.   Pareto Variates
  669.   ---------------
  670.  
  671.             Θ -(Θ+1)
  672.   f(x) = Θ a x                           Θ, a > 0; x > a
  673.  
  674.                        1/Θ
  675.   generator:  x = a / U
  676.  
  677.  
  678.   Gumbel (Extreme Value) Variates
  679.   -------------------------------
  680.  
  681.             -(x - α)/ß
  682.           -e
  683.   F(x) = e                               ß > 0
  684.  
  685.   generator:  x = α - ß log[-log(U)]
  686.  
  687.  
  688.  
  689.  
  690.  
  691.  
  692.  
  693.  
  694.  
  695.  
  696.  
  697.  
  698.  
  699.                                        9
  700.  
  701.  
  702.  
  703.  
  704.  
  705.  
  706.   Logistic Variates
  707.   -----------------
  708.  
  709.                   1
  710.   F(x) = ---------------------           ß > 0
  711.                    -(x-α)/ß
  712.               1 + e
  713.  
  714.   generator:  x = α + ß log(U)
  715.  
  716.  
  717.   Weibull Variates
  718.   ----------------
  719.  
  720.                      b
  721.               b-1 -ax
  722.   f(x) = a b x   e                       a, b, x > 0
  723.  
  724.                                1/b
  725.   generator:  x = [-log(U) / a]
  726.  
  727.  
  728.  
  729.  
  730.  
  731.  
  732.  
  733.  
  734.  
  735.  
  736.  
  737.  
  738.  
  739.  
  740.  
  741.  
  742.  
  743.  
  744.  
  745.  
  746.  
  747.  
  748.  
  749.  
  750.  
  751.  
  752.  
  753.  
  754.  
  755.  
  756.  
  757.  
  758.  
  759.  
  760.  
  761.  
  762.  
  763.                                       10